package LinkedList;//给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
//
// 图示两个链表在节点 c1 开始相交： 
//
// 
//
// 题目数据 保证 整个链式结构中不存在环。 
//
// 注意，函数返回结果后，链表必须 保持其原始结构 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, 
//skipB = 3
//输出：Intersected at '8'
//解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
//从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
//在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
// 
//
// 示例 2： 
//
// 
//
// 
//输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 
//1
//输出：Intersected at '2'
//解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
//从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
//在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
// 
//
// 示例 3： 
//
// 
//
// 
//输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
//输出：null
//解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
//由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
//这两个链表不相交，因此返回 null 。
// 
//
// 
//
// 提示： 
//
// 
// listA 中节点数目为 m 
// listB 中节点数目为 n 
// 0 <= m, n <= 3 * 10⁴ 
// 1 <= Node.val <= 10⁵ 
// 0 <= skipA <= m 
// 0 <= skipB <= n 
// 如果 listA 和 listB 没有交点，intersectVal 为 0 
// 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1] 
// 
//
// 
//
// 进阶：能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？ 
//
// 
//
// 注意：本题与主站 160 题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-
//lists/ 
// Related Topics 哈希表 链表 双指针 👍 9 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.HashSet;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
/**和面试题 02.07 链表相交相同，该题使用三种解法*/
class getIntersectionNode1 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB){
        /**
         * 哈希表，将第一个链表的节点放到哈希表中，
         * 在遍历第二个，若找到了，则直接返回
         * */
        HashSet<ListNode> set = new HashSet<>();
        while(headA!=null){
            set.add(headA);
            headA = headA.next;
        }
        while(headB!=null){
            if (set.contains(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        /**
         * 双指针，两个指针在两个链表依次后移，
         * 若两指针相等了，说明到相交位置，
         * 一旦一个到头，就重新指向另一链表头节点继续遍历
         * 如果两个链表无交点，那么最终A,B指针也会因都指向了链表末尾的null而停下，因为也相等了
         * */
        ListNode A = headA;
        ListNode B = headB;
        while (A != B){
            if(A == null){
                A = headB;
            }else{
                A = A.next;
            }

            if(B ==null){
                B = headA;
            }else{
                B = B.next;
            }

        }
        return A;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        /**
         * 得到两个链表长度，让长链表指针移动差值个位置，使两个链表剩下的长度相同
         * 因为相交节点指的是后续肯定相同
         * 然后两个指针一起移动直到相等停下，最后返回的要么是相交要么是空
         * */
        ListNode A = headA;
        ListNode B = headB;
        int lenA = 0, lenB = 0;
        while(A!=null){
            lenA++;
            A = A.next;
        }
        while(B!=null){
            lenB++;
            B = B.next;
        }
        A = headA;
        B = headB;
        //使lanA A为较长链表
        if(lenA < lenB){
            int temp = lenA;
            lenA = lenB;
            lenB = temp;

            A = headB;
            B = headA;
        }
        // 较长链表先移动
        int cap = lenA - lenB;
        while(cap>0){
            A = A.next;
            cap--;
        }
        while(A!=B){
            A = A.next;
            B = B.next;
        }
        return A;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
